package dp;

/**
 * 重点
 * 状态压缩就是把状态用二进制数字对应位的 0 1 表示，因为将一大堆状态压缩成了一个数字 因而叫状态压缩
 * dp状态转移方程
 * dp可以用for 中递归的形式完成
 *
 * 状态用一个int表示 需要的话结合一个数组标识每种状态的结果
 *   dp[state] 标识state状态下是不是稳赢
 *   状态转移方程  dp[state] = !dp[nextState]
 */
public class 我能赢么_464_状态压缩dp {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {

        if(maxChoosableInteger >= desiredTotal) return true;
        if( (1+maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
        // dp表示第i位被抽取后
        Boolean [] dp = new Boolean[1 << maxChoosableInteger];
        return dfs(maxChoosableInteger, desiredTotal, dp, 0);
    }

    private boolean dfs(int maxChoosableInteger, int desiredTotal, Boolean[] dp, int state) {

        // 可以先选2再选3  也可以先选3再选2
        if(dp[state] != null) return dp[state];

        for(int i = 1; i<= maxChoosableInteger; i++) {

            int cardIdx = 1 << (i - 1);
            // 抽过的卡不能再抽
            if((state & cardIdx)!= 0) {
                continue;
            }
            // 铁定赢了
            if(i >= desiredTotal) {
                return dp[state] = true;
            }
            // 这样选了不能判断赢了没  但是后面一种选法铁定输  那这种也是铁定赢得
            if(!dfs(maxChoosableInteger, desiredTotal -i, dp, state | cardIdx)) {
                return dp[state] = true;
            }
        }
        // 全选一遍还没赢  只能输了
        return dp[state] =false;
    }
}
